/**
 * [32] 最长有效括号
 *
 * @format
 * @lc app=leetcode.cn id=32 lang=javascript
 */

// @lc code=start
/**
 * @param {string} s
 * @return {number}
 */
// 栈·括号消除法：利用入栈记录索引，出栈消除括号
var longestValidParentheses = function (s) {
    const stack = [[".", -1]]
    const isMatched = (top, cur) => top == "(" && cur == ")"
    for (let i = 0; i < s.length; i++) {
        let top = stack.length - 1
        top == 0 || !isMatched(stack[top][0], s[i]) ? stack.push([s[i], i]) : stack.pop()
    }
    if (stack.length == 1) return s.length
    let max = 0
    for (let i = 1; i < stack.length; i++) {
        let len = stack[i][1] - stack[i - 1][1] - 1
        max = Math.max(max, len)
    }
    return Math.max(max, s.length - stack[stack.length - 1][1] - 1)
}

/* // 暴力双指针：
var longestValidParentheses = function (s) {
    let [start, end] = [0, s.length]
    while (start < end - 1) {
        while (s[start] == ")") start++
        while (s[end - 1] == "(") end--
        if (isValid(s.slice(start, end))) return end - start

    }
    return 0
} */
// debugger
// const s = "(()(((()"
// const MAX = longestValidParentheses(s)
// console.log(MAX)
// @lc code=end
